package dp

func maxProfit(prices []int) int {
	m1 := make([]*MStruct, len(prices))

	minPrice := prices[0]
	theMaxProfit := 0
	for i := range prices {
		price := prices[i]
		if price < minPrice {
			minPrice = price
		}
		profit := price - minPrice
		if profit > theMaxProfit {
			theMaxProfit = profit
		}
		m1[i] = NewMStruct(minPrice, price, theMaxProfit)
	}

	maxPrice := prices[len(prices)-1]
	theMaxProfit = 0

	result := 0
	for i := len(prices) - 1; i >= 0; i-- {
		price := prices[0]
		if price > maxPrice {
			maxPrice = price
		}
		profit := maxPrice - price
		if profit > theMaxProfit {
			theMaxProfit = profit
		}

		if m1[i].maxProfit+theMaxProfit > result {
			result = m1[i].maxProfit + theMaxProfit
		}
	}
	return result
}

type MStruct struct {
	min, current int
	maxProfit    int
}

func NewMStruct(min, current, max int) *MStruct {
	return &MStruct{
		min:       min,
		current:   current,
		maxProfit: max,
	}
}
